#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;
#define INF -1 // suppose all the weights are positive

class Graph
{
private:
    bool isWeighted;
    bool isDirected;
    int flag; // User should choose adjList or adjMatrix. adjList, flag=0; adjMatrix, flag=1; no choosing, flag=-1
    int numV;
    int numE;
    double **adjMatrix;
    int **adjMatrix_unwt; // unweighted adjacent matrix

    int iterator; // store the last place where we have created adjList items
    struct Edge_adjList
    {
        int vertex;
        int adjvex; // adjacent vertex
        double weight;
        Edge_adjList( int vertex, int adjvex, const double & weight ) 
          : vertex{ vertex }, adjvex{ adjvex }, weight{ weight } { }
    };
    Edge_adjList **adjList;

    struct Edge_adjList_unwt // unweighted adjacent list
    {
        int vertex;
        int adjvex; // adjacent vertex
        int weight;
        Edge_adjList_unwt( int vertex, int adjvex, const int & weight ) 
          : vertex{ vertex }, adjvex{ adjvex }, weight{ weight } { }
    };
    Edge_adjList_unwt **adjList_unwt;
public:
    Graph( const int _numV, const int _numE, int _flag , bool _isWeighted , bool _isDirected );
    void setEdgeWeight( int tail, int head, double weight );
    void setEdgeWeight_unwt( int tail, int head);
    void listVertexes( );
    void listEdges( );
    void wayStoring( );
    ~Graph( );
};

Graph::Graph( const int _numV, const int _numE, int _flag = -1, bool _isWeighted = true, bool _isDirected = true )
{
    this->numV = _numV;
    this->flag = _flag;
    this->isWeighted = _isWeighted;
    this->isDirected = _isDirected;

    if ( flag==-1 && _numE>_numV ) // Using adjMatrix to store data
    {
        if ( isWeighted )
        {
            adjMatrix = new double* [_numV];
            for( int i=0; i<_numV; i++ )
                adjMatrix[i] = new double[_numV];
            for( int i=0; i<_numV; i++ )
                for( int j=0; j<_numV; j++ )
                    adjMatrix[i][j] = INF;
            this->flag = 1;
        }
        else
        {
            adjMatrix_unwt = new int* [_numV];
            for( int i=0; i<_numV; i++ )
                adjMatrix_unwt[i] = new int[_numV];
            for( int i=0; i<_numV; i++ )
                for( int j=0; j<_numV; j++ )
                    adjMatrix_unwt[i][j] = 0;
            this->flag = 1;
        }   
    }
    else if( flag==-1 && _numE<_numV ) 
    {
        this->numE = _numE;
        if( isWeighted )
        {        
            this->iterator = 0;
            adjList = new Edge_adjList* [_numE];
            for (int i = 0; i < _numE; i++)
                adjList[i] = new Edge_adjList(-1, -1, -1);
            this->flag = 0;
        }
        else
        {
            this->iterator = 0;
            adjList_unwt = new Edge_adjList_unwt* [_numE];  
            for (int i = 0; i < _numE; i++)
                adjList[i] = new Edge_adjList(-1, -1, -1);
            this->flag = 0;
        }
    }
    else if( flag==1 )
    {
        if ( isWeighted )
        {
            adjMatrix = new double* [_numV];
            for( int i=0; i<_numV; i++ )
                adjMatrix[i] = new double[_numV];
            for( int i=0; i<_numV; i++ )
                for( int j=0; j<_numV; j++ )
                    adjMatrix[i][j] = INF;
        }
        else
        {
            adjMatrix_unwt = new int* [_numV];
            for( int i=0; i<_numV; i++ )
                adjMatrix_unwt[i] = new int[_numV];
            for( int i=0; i<_numV; i++ )
                for( int j=0; j<_numV; j++ )
                    adjMatrix_unwt[i][j] = 0;
        }   
    }
    else if( flag==0 )
    {
        this->numE = _numE;
        if( isWeighted )
        {
            this->iterator = 0;
            adjList = new Edge_adjList* [_numE];
            for (int i = 0; i < _numE; i++)
                adjList[i] = new Edge_adjList(-1, -1, -1);
        }
        else
        {
            this->iterator = 0;
            adjList_unwt = new Edge_adjList_unwt* [_numE];
            for (int i = 0; i < _numE; i++)
                adjList_unwt[i] = new Edge_adjList_unwt(-1, -1, -1); 
        }
    }
}
Graph::~Graph( )
{
    if( flag ) // delete a adjacent matrix
    {
        if ( isWeighted )
        {
            for( int i=0; i<numV; i++ )
                delete[] adjMatrix[i];
            delete[] adjMatrix;
        }
        else
        {
            for( int i=0; i<numV; i++ )
                delete[] adjMatrix_unwt[i];
            delete[] adjMatrix_unwt;
        }
        
    }
    else // delete a adjacent list
    {
        if ( isWeighted )
        {
            for( int i=0; i<numE; i++ )
                delete[] adjList[i];
            delete[] adjList;
        }
        else
        {
            for( int i=0; i<numE; i++ )
                delete[] adjList_unwt[i];
            delete[] adjList_unwt;
        }
    }
}

void Graph::setEdgeWeight( int tail, int head, double weight )
{
    if ( flag ) // set the weight of adjacent matrix
    {
        if ( !isWeighted ) 
            cout << "使用了错误方法，应该使用setEdgeWeight_unwt" << endl;
        else
        {
            if( isDirected )
            {
                adjMatrix[tail][head] = weight;
                numE++;
            }
            else
            {
                adjMatrix[tail][head] = weight;
                numE++;
                adjMatrix[head][tail] = weight;
                numE++;
            }
        }
    }
    else // set the weight of adjacent list
    {
        if ( !isWeighted ) 
            cout << "使用了错误方法，应该使用setEdgeWeight_unwt" << endl;
        else
        {
            if( isDirected )
            {
                if ( iterator > numE )
                    cout << "越界，不能继续插入边" << endl;
                else
                {
                    adjList[iterator]->vertex = tail;
                    adjList[iterator]->adjvex = head;
                    adjList[iterator]->weight = weight;
                    iterator++;
                }
            }
            else 
            {
                if ( iterator > numE )
                    cout << "越界，不能继续插入边" << endl;
                else
                {
                    adjList[iterator]->vertex = tail;
                    adjList[iterator]->adjvex = head;
                    adjList[iterator]->weight = weight;
                    iterator++;  
                    adjList[iterator]->vertex = head;
                    adjList[iterator]->adjvex = tail;
                    adjList[iterator]->weight = weight;
                    iterator++;
                }
            }
        }
    }
}


void Graph::setEdgeWeight_unwt( int tail, int head )
{
    if ( flag ) // set the weight of adjacent matrix
    {
        if ( isWeighted ) 
            cout << "使用了错误方法，应该使用setEdgeWeight" << endl;
        else
        {
            if( isDirected )
            {
                adjMatrix_unwt[tail][head] = 1;
                numE++;
            }
            else 
            {
                adjMatrix_unwt[tail][head] = adjMatrix_unwt[head][tail] = 1;
                numE++;
            }
        }    

    }
    else
    {
        if ( isWeighted ) 
            cout << "使用了错误方法，应该使用setEdgeWeight" << endl;
        else
        {
            if( isDirected )
                if( iterator > numE )
                cout << "越界，不能继续插入边" << endl;
                else
                {
                    adjList_unwt[iterator]->vertex = tail;
                    adjList_unwt[iterator]->adjvex = head;
                    adjList_unwt[iterator]->weight = 1;
                    iterator++;
                }
            
            else 
            {
                if ( iterator > numE )
                    cout << "越界，不能继续插入边" << endl;
                {
                    adjList_unwt[iterator]->vertex = tail;
                    adjList_unwt[iterator]->adjvex = head;
                    adjList_unwt[iterator]->weight = 1;
                    iterator++;  
                    adjList_unwt[iterator]->vertex = head;
                    adjList_unwt[iterator]->adjvex = tail;
                    adjList_unwt[iterator]->weight = 1;
                    iterator++;
                }
            }
        }
    }
}
  


void Graph::listEdges( )
{
    if ( flag==1 ) // adjacent matrix
    {
        if( isWeighted )
        {
            int itor = 0;
            cout << "边如下： " << endl;
            for( int i=0; i<numV; i++ )
                for( int j=0; j<numV; j++ )
                {
                    if( adjMatrix[i][j]!=double(INF) )
                    {
                        cout << itor << "\t";
                        cout << "( " << i << ", " << j << ", ";
                        cout << adjMatrix[i][j] << " )" << endl;
                        itor++;
                    }      
                }
        }
        else
        {
                int itor = 0;
                cout << "边如下： " << endl;
                for( int i=0; i<numV; i++ )
                    for( int j=0; j<numV; j++ )
                    {
                        if( adjMatrix_unwt[i][j]!=int(INF) )
                        {
                            cout << itor << "\t";
                            cout << "( " << i << ", " << j << ", ";
                            cout << adjMatrix[i][j] << " )" << endl;
                            itor++;
                        } 
                            
                    }
        }
    }
    else // adjacent list
    {
        if ( isWeighted )
        {
            int itor = 0;
            cout << "边如下： " << endl;
            for( int i=0; i<numE; i++ )
            {
                if ( adjList[i]->vertex != -1 )
                {
                    cout << itor << "\t";
                    cout << "( ";
                    cout << adjList[i]->vertex << ", ";
                    cout << adjList[i]->adjvex << ", ";
                    cout << adjList[i]->weight << " )" << endl;
                    itor++;
                }
                
            }
        }
        else
        {
            int itor = 0;
            cout << "边如下： " << endl;
            for( int i=0; i<numE; i++ )
            {
                if ( adjList_unwt[i]->vertex != -1 )
                {
                    cout << itor << "\t";
                    cout << "( ";
                    cout << adjList_unwt[i]->vertex << ", ";
                    cout << adjList_unwt[i]->adjvex << ", ";
                    cout << adjList_unwt[i]->weight << " )" << endl;
                    itor++;
                }
                
            }
        }
    }   
}

void Graph::listVertexes( )
{
    if ( flag==1 ) // adjacent matrix
    {
        if( isWeighted )
        {
                int a[numV];
                for( int i=0; i<numV; i++ )
                    a[numV] = 0;
                for( int i=0; i<numV; i++ )
                    for( int j=0; j<numV; j++ )
                    {
                        if( adjMatrix[i][j]!=double(INF) )
                        {
                            if( a[i]==0 )
                                a[i]++;
                            if( a[j]==0 )
                                a[j]++;
                        } 
                            
                    }
                cout << "节点如下： " << endl;
                for( int i=0; i<numV; i++ )
                    if( a[i]!=0 )
                        cout << i << " ";
                cout << endl; 
        }
        else
        {
            int a[numV];
            for( int i=0; i<numV; i++ )
                a[numV] = 0;
            for( int i=0; i<numV; i++ )
                for( int j=0; j<numV; j++ )
                {
                    if( adjMatrix_unwt[i][j]!=int(INF) )
                    {
                        if( a[i]==0 )
                            a[i]++;
                        if( a[j]==0 )
                            a[j]++;
                    } 
                        
                }
            cout << "节点如下： " << endl;
            for( int i=0; i<numV; i++ )
                if( a[i]!=0 )
                    cout << i << " ";
            cout << endl; 
        }
    }
    else
    {
        if( isWeighted )
        {
            int a[numV];
            for( int i=0; i<numV; i++ )
                a[i] = 0;
            for( int i=0; i<numE; i++ )
            {
                if ( adjList[i]->vertex != -1 )
                    if ( a[adjList[i]->vertex]==0 )
                        a[adjList[i]->vertex]++;
                if ( adjList[i]->adjvex != -1 )
                    if( a[adjList[i]->adjvex]==0 )
                        a[adjList[i]->adjvex]++;
            }
            cout << "节点如下： " << endl;
            for( int i=0; i<numV; i++ )
                if( a[i]!=0 )
                    cout << i << " ";
            cout << endl;
        }
        else
        {
            int a[numV];
            for( int i=0; i<numV; i++ )
                a[i] = 0;
            for( int i=0; i<numE; i++ )
            {
                if ( adjList_unwt[i]->vertex != -1 )
                    if ( a[adjList_unwt[i]->vertex]==0 )
                        a[adjList_unwt[i]->vertex]++;
                if ( adjList_unwt[i]->adjvex != -1 )
                    if( a[adjList_unwt[i]->adjvex]==0 )
                        a[adjList_unwt[i]->adjvex]++;
            }
            cout << "节点如下： " << endl;
            for( int i=0; i<numV; i++ )
                if( a[i]!=0 )
                    cout << i << " ";
            cout << endl;
        }
    }
}

void Graph::wayStoring( )
{
    if ( flag )
        cout << "使用邻接矩阵存储" << endl;
    else
        cout << "使用邻接表存储" << endl;
}
